package com.sunny.structure.lineartable.singlelinked;

/**
 * 实战测试1
 *
 * @author Sunny
 * @date 2020/5/12
 */
public class Test1 {

    /**
     * 反转链表
     *
     * 时间复杂度O(N)
     * 空间复杂度O(1)
     */
    public static ListNode reverseList(ListNode head) {
        ListNode pre = null;    //当前节点的上一个节点
        ListNode next = null;   //当前节点的下一个节点

        while (head != null) {
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }

    /**
     * 获取中间节点(偶数个取中间2个节点中前面的一个)
     */
    public static ListNode getMid(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;

        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    public static void main(String[] args) {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        node1.next = node2;
        node2.next = node3;

        System.out.println(getMid(node1).value);

        ListNode reverseNode = reverseList(node1);
        ListNode.traverse(reverseNode);

    }
}
